package Leetcode;

/**
 * 给你两个单词word1 和word2， 请返回将word1转换成word2 所使用的最少操作数 。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * <p>
 * 输入：word1 = "horse", word2 = "ros"
 * 输出：3
 * 解释：
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 */
public class 力扣72_编辑距离 {
    public static void main(String[] args) {
        System.out.println(minDistance2("horse", "ros"));
        System.out.println(minDistance2("intention", "execution"));
    }

    // 递归解法 自顶向下
    static int minDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        if (l1 == 0 || l2 == 0) {
            return Math.max(l1, l2);
        }
        if (word1.charAt(l1 - 1) == word2.charAt(l2 - 1)) {
            return minDistance(word1.substring(0, l1 - 1), word2.substring(0, l2 - 1));
        }
        return 1 + min(
                minDistance(word1, word2.substring(0, l2 - 1)),
                minDistance(word1.substring(0, l1 - 1), word2),
                minDistance(word1.substring(0, l1 - 1), word2.substring(0, l2 - 1)));
    }

    // 动态规划 自底向上
    static int minDistance2(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        // 有一个字符串为空串
        if (l1 * l2 == 0) {
            return l1 + l2;
        }

        // DP 数组
        int[][] op = new int[l1 + 1][l2 + 1];

        // 边界状态初始化
        for (int i = 0; i < l1 + 1; i++) {
            op[i][0] = i;
        }
        for (int j = 0; j < l2 + 1; j++) {
            op[0][j] = j;
        }

        // 计算所有 DP 值
        for (int i = 1; i < l1 + 1; i++) {
            for (int j = 1; j < l2 + 1; j++) {
                int left = 1 + op[i][j - 1];
                int down = 1 + op[i - 1][j];
                int left_down = op[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    left_down += 1;
                }
                op[i][j] = min(left, down, left_down);
            }
        }

        return op[l1][l2];
    }


    static int min(int a, int b, int c) {
        return a < b ? Math.min(a, c) : Math.min(b, c);
    }

}
